package leetcode_900;

import java.util.Arrays;

/**
 *@author 周杨
 *MostProfitAssigningWork_826 给定n个工人的能力 问能在不超过能力的情况下 拿到最多的工资方案
 *describe:排序用贪心 AC 54%
 *2018年10月30日 上午10:40:41
 */
public class MostProfitAssigningWork_826 {
	class Work{
		int difficulty;
		int profit;
		public Work(int difficulty,int profit) {
			this.difficulty=difficulty;
			this.profit=profit;
		}
	}
	public int maxProfitAssignment(int[] difficulty, int[] profit, int[] worker) {
		Work [] works=new Work[difficulty.length];
        for(int i=0;i<difficulty.length;++i) {
        	Work word=new Work(difficulty[i], profit[i]);
        	works[i]=word;
        }
        Arrays.sort(works,(o1,o2)->o1.difficulty-o2.difficulty);
        Arrays.sort(worker);
        int best=0,res=0,index=0;//best记录上次最优解 index是不会回退的 因为前面的最优解已经被保存
        for(int w:worker) {
        	while(index<works.length&&w>=works[index].difficulty) {
        		best=Math.max(works[index++].profit, best);
        	}
        	res+=best;
        }
        return res;
    }
}
